package test;

/**
 * @author 豆包LU
 * @date 2023/4/11 9:47
 */
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

class LFUCache<K, V> {

    /**
     * Desc:缓存容量
     * @author 豆包LU
     * @date 2023/4/11 9:50
     */
    private final int capacity;
    // 缓存数据，使用 HashMap 存储键值对
    private final HashMap<K, V> cache;
    // 存储键的使用频率，使用 LinkedHashMap 保持插入顺序
    private final LinkedHashMap<K, Integer> frequencyMap;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.frequencyMap = new LinkedHashMap<>();
    }

    public V get(K key) {
        if (!cache.containsKey(key)) {
            // 缓存中不存在该键，返回 null
            return null;
        }

        // 更新键的使用频率
        updateFrequency(key);
        // 返回键对应的值
        return cache.get(key);
    }

    public void put(K key, V value) {
        if (capacity == 0) {
            // 缓存容量为 0，直接返回
            return;
        }

        // 缓存中存在键，更新值并更新使用频率
        if (cache.containsKey(key)) {
            cache.put(key, value);
            updateFrequency(key);
        }
        // 缓存中不存在键
        else {
            // 如果缓存容量已满，根据使用频率移除最不经常使用的键
            if (cache.size() == capacity) {
                // 获取使用频率最低的键
                frequencyMap.entrySet().stream()
                        .sorted(Map.Entry.comparingByValue())
                        .findFirst()
                        .ifPresent(entry -> {
                            K lfuKey = entry.getKey();
                            // 从缓存中移除最不经常使用的键
                            cache.remove(lfuKey);
                            // 从频率映射表中移除最不经常使用的键
                            frequencyMap.remove(lfuKey);
                        });
            }
            // 将新的键值对加入缓存
            cache.put(key, value);
            // 新加入的键的使用频率初始化为 0
            frequencyMap.put(key, 0);
        }
    }

    // 更新键的使用频率
    private void updateFrequency(K key) {
        // 获取当前键的使用频率
        int frequency = frequencyMap.get(key);
        // 更新键的使用频率为当前频率加 1
        frequencyMap.put(key, frequency + 1);
    }
    public int getFrequency(K key) {
        // 获取当前键的使用频率
        int frequency = frequencyMap.get(key);
        return frequency;
    }

    public static void main(String[] args) {
        // 创建容量为 3 的 LFU 缓存
        LFUCache<Integer, String> cache = new LFUCache<>(3);

        cache.put(1, "one");
        cache.put(2, "two");
        cache.put(3, "three");
        cache.get(1);
        cache.get(2);
        cache.get(2);
        LinkedHashMap<Integer, Integer> frequencyMap = cache.frequencyMap;
        System.out.println(frequencyMap);
        cache.put(4,"four");
        System.out.println(frequencyMap);
        cache.get(4);
        cache.get(4);
        cache.put(5,"five");
        System.out.println(frequencyMap);
        cache.get(5);
        cache.get(5);
        cache.put(6,"six");
        System.out.println(frequencyMap);
    }
}

